package com.xyhuo.leetcode;

public class MostPoints {

    public long mostPointsOld(int[][] questions) {
        int len = questions.length;
        int[] db = new int[len];
        db[0] = questions[0][0];
        int result = db[0];
        for (int i = 1; i < len; i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                if (j + questions[j][1] < i && db[j] > tmp) {
                    tmp = db[j];
                }
            }
            db[i] = tmp + questions[i][0];
            if (db[i] > result) {
                result = db[i];
            }
        }
        return result;
    }

    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[Math.min(n, i + questions[i][1] + 1)]);
        }
        return dp[0];
    }


    public static void main(String[] args) {
        int[][] q1 = {{21, 2}, {1, 2}, {12, 5}, {7, 2}, {35, 3}, {32, 2}, {80, 2}, {91, 5}, {92, 3}, {27, 3}, {19, 1}, {37, 3}, {85, 2}, {33, 4}, {25, 1}, {91, 4}, {44, 3}, {93, 3}, {65, 4}, {82, 3}, {85, 5}, {81, 3}, {29, 2}, {25, 1}, {74, 2}, {58, 1}, {85, 1}, {84, 2}, {27, 2}, {47, 5}, {48, 4}, {3, 2}, {44, 3}, {60, 5}, {19, 2}, {9, 4}, {29, 5}, {15, 3}, {1, 3}, {60, 2}, {63, 3}, {79, 3}, {19, 1}, {7, 1}, {35, 1}, {55, 4}, {1, 4}, {41, 1}, {58, 5}};

        int[][] questions = {{21, 5}, {92, 3}, {74, 2}, {39, 4}, {58, 2}, {5, 5}, {49, 4}, {65, 3}};
        MostPoints m = new MostPoints();
        m.mostPoints(q1);
    }
}
